// Knapsack Problem

#include<iostream>
using namespace std;

//int w[] = {4,5,6,7,8,9};
//int b[] = {2,3,4,2,3,6};
//int bw[sizeof(w)/sizeof(int)][1000];
int benw(int k);
int  benw(int i, int j);

int main()
{
	int w[] = {4,5,6,7,8,9};
	int b[] = {2,3,4,2,3,6};
	int k;
	cout << "\nEnter the weight : ";
	cin >> k;
	cout << "\nThe Max Benefit for given weight is: " << benw(w,b, sizeof(w)/sizeof(int), k) << "\n"; 
	return 0;
}

int benw(int w[], int b[], int length, int k)
{
	int sumw =0;
	for(int i=0; i<length; i++)
	sumw = w[i]+sumw;
	int **bw = new int*[length];
	for(int i=0; i<length; i++)
	bw[i] = new int[sumw+1];
	
	for(int i=0; i< length; i++)
	{
		for(int j=0; j<=sumw; j++)
		bw[i][j] = -1;
	}
	int max =0;
	max = benw(sizeof(w)/sizeof(int) -1, k);
	
	delete[] bw
	return max;
}

int benw(int i, int k)
{
	if(i<0 || k<=0)
	return 0;
	
	if(bw[i][k]!=-1)
	return bw[i][k];
	
	if(w[i]>k)
	return benw(i-1,k);
	
	bw[i][k] = benw(i-1,k) > b[i]+benw(i-1,k-w[i])? benw(i-1,k): b[i]+benw(i-1,k-w[i]);
	return bw[i][k];
}
